package nu.aing.P20140701;

import java.util.Arrays;

import nu.aing.utils.TestUtils;

/**
 * @author memekmaut@gmail.com
 */
public class BuildingHeightsEasy {
    
    public static void main(String[] args) {
        
        BuildingHeightsEasy obj = new BuildingHeightsEasy();
        TestUtils.test(obj, "minimum",
                2, 
                new int[] {1, 2, 1, 4, 3}
        );
        TestUtils.test(obj, "minimum",
                3, 
                new int[] {1, 3, 5, 2, 1}
        );
        TestUtils.test(obj, "minimum",
                1, 
                new int[] {43, 19, 15}
        );
        TestUtils.test(obj, "minimum",
                3, 
                new int[] {19, 23, 9, 12}
        );
        TestUtils.test(obj, "minimum",
                12, 
                new int[] {25, 18, 38, 1, 42, 41, 14, 16, 19, 46, 42, 39, 38, 31, 43, 37, 26, 41, 33, 37, 45, 27, 19, 24, 33, 11, 22, 20, 36, 4, 4}
        );
        
    }
    
    public int minimum(int M, int[] heights) {
        Arrays.sort(heights);
        int pt = 0;
        for(int i = heights.length -1; i > 0; i--) {
            int s = heights[i], t = 0, c = 1;
            for(int j = i - 1; j >= 0; j--) {
                t += s - heights[j];
                if(++c == M) {
                    pt = (pt == 0) ? t : (pt < t) ? pt : t;
                    break;
                }
            }
        }
        return pt;
    }
    
}
